1. Field of the Invention
The present invention relates to a content addressable memory device (hereinafter referred to CAM) for storing ternary data. Particularly, the present invention relates to a CAM which writes data onto a data cell and a mask cell by a single write cycle when a ternary CAM cell is used as a binary CAM cell.
2. Description of the Related Art
With the wide-spread use of the Internet, a high-speed requirement is increasing on network relay devices, such as a switching hub and a router. To meet a high-speed requirement, the relay device frequently uses a CAM for address filtering and classification of packets.
Specifically, CAMs are used in a search process in layers 2, 3, and 4 of the OSI (Open System Interconnection) of a network. Conventional binary CAMs having xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d are sufficient in some search processes, but ternary CAMs having xe2x80x9cdon""t carexe2x80x9d in addition to xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d are needed in other search processes.
The ternary CAMs are disclosed in U.S. Pat. No. 6,154,384 and Japanese Patent Application Publication No. 7-220483, for example.
According to U.S. Pat. No. 6,154,384 as shown in FIG. 8, a ternary CAM cell unit 70 includes a main cell 72 for storing data, a mask cell 74 for storing mask data, a comparator 76 for comparing data held in the main cell 72 with search data supplied through a pair of search (comparison) data lines CMP and CMPB, a mask circuit 78 for controlling whether or not to output the result of the comparison of the comparator 76 to a match line in response to a logical state of mask data held in the mask cell 74, and a precharge circuit 80 for precharging the match line.
A pair of complementary data bit lines BL and BLB, supplied with data to be stored in the main cell 72 and data to be stored in the mask cell 74, are connected to each of the main cell 72 and the mask cell 74. A main word line for selecting the main cell 72 is connected to the main cell 72. A mask word line for selecting the mask cell 74 is connected to the mask cell 74.
When mask data indicating an unmask state is stored in the mask cell 74 in the ternary CAM cell unit 70, the result of the comparison of the comparator 76 is output to the match line the same as in the conventional binary CAM. When mask data indicating a mask state is set in the mask cell 74, the comparator 76 is electrically isolated from the match line by the mask circuit 78, and the match line remains in a match state. In other words, the match line is at a xe2x80x9cdon""t carexe2x80x9d state.
According to Japanese Patent Application Publication No. 7-220483 shown in FIG. 9, a ternary CAM cell unit 82 includes two memory cells 84 and 86 for storing two bit data, and a match detector circuit 88. A pair of bit lines BL1 and BL1/ are connected to the one memory cell 84, and a pair of bit lines BL2 and BL2/ are connected to the other memory cell 86. One word line W is commonly connected to the two memory cells 84 and 86.
In the ternary CAM cell unit 82, the xe2x80x9cdon""t carexe2x80x9d state is assigned to two bit data xe2x80x9c0,0xe2x80x9d stored in the two memory cells 84 and 86, the xe2x80x9c0xe2x80x9d state is assigned to the two bit data of xe2x80x9c0,1xe2x80x9d and the xe2x80x9c1xe2x80x9d state is assigned to two bit data of xe2x80x9c1,0xe2x80x9d.
When xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d is stored in the two memory cells 84 and 86 as the ternary data, the match detector circuit 88 compares the ternary data of xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d with search data. The result of the comparison is output to the match line (not shown) as a signal MV. Specifically, when a match is detected, the signal MV (a voltage at the match line) holds the precharged xe2x80x9c1xe2x80x9d state. When an unmatch is detected, the match line is discharged to xe2x80x9c0xe2x80x9d.
When the xe2x80x9cdon""t carexe2x80x9d state is stored as the ternary data, the match detector circuit 88 is electrically isolated from the match line, and the signal MV remains precharged at xe2x80x9c1xe2x80x9d, namely, the match state is maintained.
When the ternary CAM cell units 70 and 82 are used as a binary CAM cell, the ternary CAM cell unit 70 shown in FIG. 8 must store the binary data in the main cell 72 and the mask data in the unmask state in the mask cell 74. The ternary CAM cell unit 82 shown in FIG. 9 must store xe2x80x9c0,1xe2x80x9d or xe2x80x9c1,0xe2x80x9d in the two memory cells 84 and 86. In comparison with conventional binary CAM, the number of settings of data is doubled.
U.S. Pat. No. 6,108,227 proposes another ternary CAM cell.
Referring to FIG. 10, a ternary CAM cell unit 90 has a mode in which a comparator 76 outputs the result of the comparison to the match line in response to a signal MODE regardless of the state of the mask data, in addition to the ternary CAM cell unit 70 shown in FIG. 8. When the ternary CAM cell unit 90 is used as a binary CAM cell, it suffices to store data in the main cell 72. In other words, the ternary CAM cell unit 90 is used as a binary CAM cell by a single write operation.
However, this ternary CAM cell unit 90 requires the mask circuit 78 which outputs, to the match line, the result of the comparison of the comparator 76 regardless of the state of the mask data in response to the signal MODE. As the result, the area of the CAM cell increases inebitably.
The requirement for a larger capacity on the CAM is mounting, and an increase in the cell area is a serious problem. There is a need for a ternary CAM cell which requires no redundant write cycle of mask data when used as a binary CAM cell and is free from an increase in the cell area.
Accordingly, it is an object of the present invention to provide a content addressable memory device which allows a ternary CAM cell to be used as a binary CAM cell by a single write cycle without requiring an increase in the scale of a circuit.
In one aspect of the present invention, a content addressable memory device incudes at least one ternary content addressable memory cell unit which stores one of ternary data of xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d, and xe2x80x9cdon""t carexe2x80x9d states, wherein the ternary content addressable memory cell unit includes a data cell for storing binary data of xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d and a mask cell for storing mask data that masks the binary data from a searching operation, and a write circuit which writes the binary data to the data cell while writing the mask data in an unmask state to the mask cell at the same time when the binary data is written to the ternary content addressable memory cell unit.
Preferably, the content addressable memory device includes at least one ternary content addressable memory cell unit which stores one of ternary data of xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d, and xe2x80x9cdon""t carexe2x80x9d states, wherein the ternary content addressable memory cell unit includes a data cell for storing data supplied through a data bit line, and a mask cell for storing mask data that is supplied through a mask bit line and masks the content addressable memory cell unit from a searching operation, and a comparator which compares the data stored in the data cell with search data, and outputs the result of the comparison if the mask data in the unmask state is stored in the mask cell, and outputs a match as the result of the comparison if the mask data in a mask state is stored in the mask cell.
When the ternary data is written into the ternary content addressable memory cell unit, the mask data is written into the mask cell independently of the writing of the data into the data cell. On the contrary, when the binary data is written into the ternary content addressable memory cell unit, the mask data in an unmask state is written into the mask cell while the data is written into the data cell at the same time.
The content addressable memory device includes a write circuit. The write circuit preferably includes a first write driver which supplies the data bit line with the data to be stored in the data cell, and a second write driver which supplies the mask bit line with the mask data to be stored in the mask cell. Each of the data cell and the mask cell preferably is of a static random-access memory type, and each of the data bit line, and the mask bit line preferably is a complementary bit line pair.
In another aspect of the present invention, a content addressable memory device includes at least one ternary content addressable memory cell unit for storing ternary data, wherein the ternary content addressable memory cell unit includes a first data cell for storing first data, and a second data cell for storing second data, a comparator which compares ternary data of xe2x80x9c1xe2x80x9d, xe2x80x9c0xe2x80x9d, and xe2x80x9cdon""t carexe2x80x9d, assigned by the first and second data, with search data, and outputs the result of the comparison if the ternary data is xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d, or always outputs a match if the ternary data is xe2x80x9cdon""t carexe2x80x9d. When binary data is written into the ternary content addressable memory cell unit, the same data is written to the first data cell and the second data cell.
When the ternary data is written on the ternary content addressable memory cell unit, the second data is preferably written to the second data cell independently of the writing of the first data to the first data cell.
Preferably, the ternary data of one of xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d is assigned to the first and second data of xe2x80x9c0,0xe2x80x9d, the ternary data of the other of xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d is assigned to the first and second data of xe2x80x9c1,1xe2x80x9d, and the ternary data of xe2x80x9cdon""t carexe2x80x9d is assigned to one of the first and second data of xe2x80x9c0,1xe2x80x9d and xe2x80x9c1,0xe2x80x9d.
Preferably, the ternary content addressable memory cell unit further includes a first data bit line which is connected to the first data cell, and is supplied with the first data to be stored in the first data cell, a second data bit line which is connected to the second data cell and is supplied with the second data to be stored in the second data cell, and a word line which is connected to the first data cell and the second data cell, and concurrently selects the first and second data cells.
Preferably, each of the data cell and the mask cell is of a static random-access memory type, and each of the data bit line and the mask bit line is a complementary bit line pair.
The ternary content addressable memory device includes a write circuit. The write circuit preferably includes a write driver for supplying data, a first column gate which supplies the first data bit line pair with the data supplied by the write driver as the first data, and a second column gate which supplies the second data bit line pair with the data supplied by the write driver as the second data.
Preferably, the ternary content addressable memory cell unit further includes a first word line for selecting the first data cell, connected to the first data cell, a second word line for selecting the second data cell, connected to the second data cell, and a data bit line connected to the first data cell and the second data cell, and supplied with data to be stored in the first data cell and the second data cell. When the content addressable memory cell is of a SRAM type, the common data bit line is preferably a complementary bit line pair.